Discrete Mathematics
Q41.
Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,...,100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then, y+ 10z = _____.Q43.
Consider the function y=|x| in the interval [-1, 1]. In this interval, the function isQ44.
Let G be a simple, finite, undirected graph with vertex set \{v_1,...,v_n\}. Let \Delta (G) denote the maximum degree of G and let N=\{1,2,...\} denote the set of all possible colors. Color the vertices of G using the following greedy strategy: for i = 1,...,n color(v_i)\leftarrow min\{ j \in N: \text{ no neighbour of } v_i \text{ is colored } j\} Which of the following statements is/are TRUE?Q45.
Let G be an undirected complete graph on n vertices, where n\gt2. Then, the number of different Hamiltonian cycles in G is equal toQ46.
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is .Q47.
Graph G is obtained by adding vertex s to K_{3,4} and making s adjacent to every vertex of K_{3,4}. The minimum number of colours required to edge-colour G is _______Q48.
Let A and B be sets with cardinalities m and n respectively. The number of one-one mappings from A to B, when m \lt n, isQ50.
How many onto (or surjective) functions are there from an n-element ( n \geq 2 ) set to a 2-element set?